struct SkiplistNode{
    int _val;
    vector<SkiplistNode*> _nextV;
    SkiplistNode(int val,int num)
        :_val(val),_nextV(num,nullptr)
    {}
};
class Skiplist {
typedef SkiplistNode Node;
private:
    Node* _head;
    int _maxnum;
    double _p;
private:
    //生成一个随机层数,按照规则
    int random(){
        int level = 1;
        while(rand() < RAND_MAX*_p && level < _maxnum){
            level++;
        }
        return level;
    }
public:
    Skiplist(int maxnum = 32,double p = 0.25)
        :_maxnum(maxnum),_p(p)
    {
        srand(time(nullptr));
        _head = new Node(-1,1);
    }
    
    bool search(int target) {
        //从头节点的最高层开始找
        int level = _head->_nextV.size()-1;
        Node* cur = _head;
        while(level >= 0){
            if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target){
                level--;
            }else if(cur->_nextV[level]->_val < target){
                cur = cur->_nextV[level];
            }else{
                return true;
            }
        }
        return false;
    }
    
    void add(int num) {
        //找到要添加节点位置的每一层的前一个节点
        vector<Node*> prevV(_maxnum,_head);
        //按照查找的逻辑。我每次向下一层查找时，当前节点就是我的要插入的节点的这一层的前一个节点
        int level = _head->_nextV.size()-1;
        Node* cur = _head;
        while(level >= 0){
            if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num){
                prevV[level]=cur;
                level--;
            }else if(cur->_nextV[level]->_val < num){
                cur = cur->_nextV[level];
            }
        }
        //生成节点信息
        int n = random();
        if(n > _head->_nextV.size()){
            _head->_nextV.resize(n);
        }
        Node* newnode = new Node(num,n);
        for(int i = 0 ; i < n ; i++){
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }
    
    bool erase(int num) {
        //删除时候，也要找到删除节点的每一层的前一个节点信息 vector<Node*> prevV(_maxnum,_head);
        //按照查找的逻辑。我每次向下一层查找时，当前节点就是我的要插入的节点的这一层的前一个节点
        vector<Node*> prevV(_maxnum,_head);
        int level = _head->_nextV.size()-1;
        Node* cur = _head;
        while(level >= 0){
            if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num){
                prevV[level]=cur;
                level--;
            }else if(cur->_nextV[level]->_val < num){
                cur = cur->_nextV[level];
            }
        }
        //找不到节点
        if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){
            return false;
        }
        //找到节点
        Node* erase_node = prevV[0]->_nextV[0];
        for(int i = 0 ; i < erase_node->_nextV.size() ; i++){
            prevV[i]->_nextV[i] = erase_node->_nextV[i];
        }
        delete erase_node;
        return true;
    }
};